Cloud architectures are used in cloud computing and cloud storage systems for offering infrastructure-as-a-service (IaaS) cloud services. Examples of cloud architectures include the VMware vCloud Director® cloud architecture software, Amazon EC2™ web service, and OpenStack™ open source cloud computing service. IaaS cloud service is a type of cloud service that provides access to physical and/or virtual resources in a cloud environment. These services provide a tenant application programming interface (API) that supports operations for manipulating IaaS constructs such as virtual computing instances, which may be virtual machines (VMs) that contain a guest operating system (OS) or OS-less containers, and logical networks. However, the use of such public cloud services is typically kept separate from the use of existing computing resources in data centers managed by an enterprise.
When migrating large numbers of virtual computing instances from a private data center to a public cloud, large enterprises face challenges in predicting the performance of a system during migration. Since in most cases operations must be more or less uninterrupted during the migration, the unknown performance of the system during the migration is a source of risk to the on-going operation. In some cases, enterprises decide to delay or forgo the planned migration, electing instead to move some small portion of the group of virtual computing instances that is not central to the operation.
The nature of the problem is one of selecting a permutation that has good performance characteristics when applied as an ordering of virtual computing instances being migrated. Since the naive implementation operates in factorial time with respect to the number of virtual computing instances, it is not practical for large operations, as the solution would require many years to run to completion. Parallel computation also would yield only incremental improvement for vast expenditures of resources.
The N-factorial nature of the problem is shared by the well-known “Travelling Salesman Problem” (hereinafter, TSP), with important differences, however. In both cases, a fully connected graph is considered, and only select edges of that graph are traversed to form the solution. Unlike the TSP, the cost of traversing a graph edge of the migration problem is not constant. In general, it depends on the migration status of the whole set of virtual computing instances. Thus, each time a virtual computing instance is migrated, the costs associated with the various graph edges change. Given the large number of virtual computing instances that enterprises employ, the brute force combinatorial approach is of no use, and a migration solution using the TSP solver does not yet exist.